/**
 * @file dsets.cpp
 * @author xincz
 * @brief 
 * @version 0.1
 * @date 2021-05-31
 * 
 * @copyright Copyright (c) 2021
 * 
 */

#include "dsets.h"


void DisjointSets::MakeSet(int x) {
    parent[x] = x;
    sizes[x] = 1;
}


void DisjointSets::AddElements(int num) {
    capacity += num;
    parent.reserve(capacity);
    sizes.reserve(capacity);

    for (int i=0; i<num; i++) {
        parent.emplace_back(-1);
        sizes.emplace_back(0);
    }
}


int DisjointSets::Find(int elem) {
    if (parent[elem] == elem) return elem;  // if a root, return
    return parent[elem] = Find(parent[elem]);  // Find the root and path compress
}


void DisjointSets::Union(int a, int b) {
    // Find roots
    a = Find(a);
    b = Find(b);

    // Check for self assignment
    if (a == b) return;

    // Union by size
    if (sizes[a] < sizes[b]) {
        parent[a] = b;
        sizes[b] += sizes[a];
    } else {
        parent[b] = a;
        sizes[a] += sizes[b];
    }
}
